package LC;

/**
 * @ClassName TestzX
 * @Description: TODO
 * @Author hl
 * @Date 2020/8/31
 * @Version V1.0
 **/
public class TestzX {
    public static void main(String[] args) {
        int []a={1,2,4,3,5,6};
        System.out.println( InversePairs_2(a));
    }
    public static int times = 0;

    public static int InversePairs_2(int[] array) {
        if (array != null && array.length > 0) {
            mergeSortUp2Down(array, 0, array.length - 1);
        }
        return times;

    }

    public static void mergeSortUp2Down(int[] elem, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;

        mergeSortUp2Down(elem, start, mid);
        mergeSortUp2Down(elem, mid + 1, end);

        merge(elem, start, mid, end);
    }

    public static void merge(int[] elem, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while (i <= mid && j <= end) {
            if (elem[i] <= elem[j]) {
                temp[k++] = elem[i++];
            } else {
                temp[k++] = elem[j++];
                times += mid - i + 1; // core code, calculate InversePairs
                times %= 1000000007;
            }
        }
    }
}
